namespace PF {
    export abstract class JumpPointFinderBase {
        trackJumpRecursion: boolean;
        startNode: Node;
        endNode: Node;
        grid: Grid;
        heuristic: Function;
        openList: Heap<Node>;
        constructor(opt?: IJumpPointFinderOptions) {
            opt = opt || {};
            this.heuristic = opt.heuristic || Heuristic.manhattan;
            this.trackJumpRecursion = opt.trackJumpRecursion || false;
        }

        findPath(startX: number, startY: number, endX: number, endY: number, grid: Grid) {
            var openList = this.openList = new Heap<Node>(function (nodeA, nodeB) {
                return nodeA.f - nodeB.f;
            }),
                startNode = this.startNode = grid.getNodeAt(startX, startY),
                endNode = this.endNode = grid.getNodeAt(endX, endY), node;

            this.grid = grid;


            // set the `g` and `f` value of the start node to be 0
            startNode.g = 0;
            startNode.f = 0;

            // push the start node into the open list
            openList.push(startNode);
            startNode.opened = true;

            // while the open list is not empty
            while (!openList.empty) {
                // pop the position of node which has the minimum `f` value.
                node = openList.pop();
                node.closed = true;

                if (node === endNode) {
                    return Util.expandPath(Util.backtrace(endNode));
                }

                this._identifySuccessors(node);
            }

            // fail to find the path
            return [];
        }

        private _identifySuccessors(node: Node) {
            var grid = this.grid,
                heuristic = this.heuristic,
                openList = this.openList,
                endX = this.endNode.x,
                endY = this.endNode.y,
                neighbors, neighbor,
                jumpPoint, i, l,
                x = node.x, y = node.y,
                jx, jy, dx, dy, d, ng, jumpNode,
                abs = Math.abs, max = Math.max;

            neighbors = this._findNeighbors(node);
            for (i = 0, l = neighbors.length; i < l; ++i) {
                neighbor = neighbors[i];
                jumpPoint = this._jump(neighbor[0], neighbor[1], x, y);
                if (jumpPoint) {

                    jx = jumpPoint[0];
                    jy = jumpPoint[1];
                    jumpNode = grid.getNodeAt(jx, jy);

                    if (jumpNode.closed) {
                        continue;
                    }

                    // include distance, as parent may not be immediately adjacent:
                    d = Heuristic.octile(abs(jx - x), abs(jy - y));
                    ng = node.g + d; // next `g` value

                    if (!jumpNode.opened || ng < jumpNode.g) {
                        jumpNode.g = ng;
                        jumpNode.h = jumpNode.h || heuristic(abs(jx - endX), abs(jy - endY));
                        jumpNode.f = jumpNode.g + jumpNode.h;
                        jumpNode.parent = node;

                        if (!jumpNode.opened) {
                            openList.push(jumpNode);
                            jumpNode.opened = true;
                        } else {
                            openList.updateItem(jumpNode);
                        }
                    }
                }
            }
        }

        protected abstract _findNeighbors(node: Node): Array<Array<number>>;
        protected abstract _jump(x: number, y: number, px: number, py: number);
    }
}

interface IJumpPointFinderOptions {
    heuristic?: Function;
    trackJumpRecursion?: boolean
}